{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 决策树\n",
    "\n",
    "- 优点： 计算复杂度不高， 输出结果易于理解， 对中间值的缺失不敏感， 可以处理不相关特征数据。\n",
    "- 缺点： 可能会产生过度匹配问题。\n",
    "- 适用数据类型： 数值型和标称型。\n",
    "\n",
    "## 创建分支的伪代码函数createBranch()如下所示\n",
    "\n",
    "```python\n",
    "检测数据集中的每个子项是否属于同一分类：\n",
    "    if so return 类标签；\n",
    "    else\n",
    "        寻找划分数据集的最好特征\n",
    "        划分数据集\n",
    "        创建分支节点\n",
    "            for 每个划分的子集\n",
    "                 调用函数createBranch并增加返回结果到分支节点中\n",
    "    return 分支节点\n",
    "```\n",
    "上面的伪代码createBranch是一个递归函数， 在倒数第二行直接调用了它自己。 \n",
    "\n",
    "## 决策树的一般流程\n",
    "\n",
    "1. 收集数据： 可以使用任何方法。\n",
    "2. 准备数据： **树构造算法只适用于标称型数据， 因此数值型数据必须离散化。**\n",
    "3. 分析数据： 可以使用任何方法， 构造树完成之后， 我们应该检查图形是否符合预期。\n",
    "4. 训练算法： 构造树的数据结构。\n",
    "5. 测试算法： 使用经验树计算错误率。\n",
    "6. 使用算法： 此步骤可以适用于任何监督学习算法， 而使用决策树可以更好地理解数据的内在含义。\n",
    "\n",
    "\n",
    "**[ID3维基百科](http://en.wikipedia.org/wiki/ID3_algorithm)**\n",
    "\n",
    "## 特征选择\n",
    "- 熵/香农熵（entropy）\n",
    "\n",
    "$$\n",
    "H=-\\sum_{i=1}^{n}\\quad P(x_i) log_2P(x_i)\n",
    "$$\n",
    "\n",
    "- 信息增益（information gain）\n",
    "在划分数据集之前之后信息发生的变化称为信息增益， 知道如何计算信息增益， 我们就可以计算每个特征值划分数据集获得的信息增益， **获得信息增益最高的特征就是最好的选择**。\n",
    "\n",
    "- 基尼不纯度（Gini impurity）\n",
    "简单地说就是从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.970950594455\n",
      "1.37095059445\n"
     ]
    }
   ],
   "source": [
    "# 熵的计算\n",
    "from math import log\n",
    "\n",
    "def calcShannonEnt(dataSet):\n",
    "    numEntries = len(dataSet)\n",
    "    labelCounts = {}\n",
    "    #❶ （以下五行） 为所有可能分类创建字典\n",
    "    for featVec in dataSet:\n",
    "        currentLabel = featVec[-1]       # 使用最后一列\n",
    "        if currentLabel not in labelCounts.keys():\n",
    "            labelCounts[currentLabel] = 0\n",
    "        labelCounts[currentLabel] += 1\n",
    "    shannonEnt = 0.0\n",
    "    for key in labelCounts:\n",
    "        prob = float(labelCounts[key])/numEntries\n",
    "        shannonEnt -= prob * log(prob,2) #❷ 以2为底求对数\n",
    "    return shannonEnt\n",
    "\n",
    "def createDataSet():\n",
    "    dataSet = [[1, 1, 'yes'],\n",
    "               [1, 1, 'yes'],\n",
    "               [1, 0, 'no'],\n",
    "               [0, 1, 'no'],\n",
    "               [0, 1, 'no']]\n",
    "    labels = ['no surfacing','flippers']\n",
    "    #change to discrete values\n",
    "    return dataSet, labels\n",
    "\n",
    "myDat,labels=createDataSet()\n",
    "print(calcShannonEnt(myDat))\n",
    "\n",
    "# 熵越高，则混合的数据也越多,当平均分布时，熵最大\n",
    "myDat[0][-1]='maybe'    #多加了个种类\n",
    "print(calcShannonEnt(myDat))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
